// demo2.搅乱顺序儿童按照体重重排
// 搅乱顺序的一群儿童成一个队列。每个儿童由一个整数对{w,k}
// w表示体重，k是排在这个儿童前面体重大于等于w的儿童数。
// 输入 {8,0},{4,4},{8,1},{5,0},{6,1},{5,2},
// 输出 {5,0},{8,0},{5,2},{6,1},{4,4},{8,1},

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> Child;
vector<Child> ReconstructQueue(const vector<vector<int>>& people) {
    vector<Child> vt;
    for (auto p : people) vt.push_back(p);
    auto cmp = [](Child a, Child b){
        if (a[0]==b[0]) return a[1]<b[1];
        return a[0]>b[0];
    };
    sort(vt.begin(), vt.end(), cmp);
    vector<Child> ans;
    for (size_t i=0; i<vt.size(); i++) {
        ans.insert(ans.begin() + vt[i][1], vt[i]);
    }
    return ans;
}
